//给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。 
//
// 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下： 
//
// 
// "123" 
// "132" 
// "213" 
// "231" 
// "312" 
// "321" 
// 
//
// 给定 n 和 k，返回第 k 个排列。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3, k = 3
//输出："213"
// 
//
// 示例 2： 
//
// 
//输入：n = 4, k = 9
//输出："2314"
// 
//
// 示例 3： 
//
// 
//输入：n = 3, k = 1
//输出："123"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 1 <= k <= n! 
// 
//
// Related Topics 递归 数学 👍 796 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ldltd
 * @date 2023-08-26 02:50:30
 * @description 60.排列序列
 */
public class PermutationSequence{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new PermutationSequence().new Solution();
			List<Integer> raa=new ArrayList<Integer>();
			raa.add(1);
			raa.add(2);
		 System.out.println(solution.getPermutation(3, 3));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 int count;
		 boolean []vis;
		 String ans;
		 /*全排列回溯*/
    public String getPermutation(int n, int k) {
		List<Integer> res=new ArrayList<>();
		this.vis=new boolean[n];
		dfs(n,0,res,k);

		return ans;
    }
	private void  dfs(int n,int dep , List<Integer> res,int k){

		if(dep==n){
			count++;
			if(count==k){
				StringBuffer buffer = new StringBuffer();
				for (Integer integer : res) {
					buffer.append(integer);
				}
				ans=buffer.toString();
			}else {
				return;
			}
		}
		for (int i = 1; i <=n; i++) {
			if(!vis[i-1]){
				res.add(i);
				vis[i-1]=true;
				dfs(n,dep+1,res,k);
				vis[i-1]=false;
				res.remove(res.size()-1);
			}
		}
	}
	//阶乘数组
	/*回溯+剪枝  时间On2空间on
	* 比如三个数。每个数都有2！个排列
	* 用一个数组去保存到每一个数时，阶乘的大小
	* 比如求第3种排列，则2!=2,因此不是第一个数开头*/
	private int [] factorial;
	public String getPermutation1(int n, int k) {
		calculateFactorial(n);
		// 查找全排列需要的布尔数组
		vis = new boolean[n];
		StringBuilder path = new StringBuilder();
		dfs1(n,0, k,path);
		return path.toString();
	}
	private void dfs1(int n,int dep,int k,StringBuilder path){
		if(dep==n) return;
		//计算还没确定的数字全排列个数，第一次进入的是n-1，比如1234，选择1，则没选的有3个
		int cnt=factorial[n-1-dep];
		for (int i = 1; i <=n; i++) {
			if(vis[i]){
				continue;
			}
			//如果当前阶乘小于k，说明不在这一层，减去当前层的阶乘数
			if(cnt<k){
				k-=cnt;
				continue;
			}
			//如果小于等于当前阶乘数，就说明在这一层
			path.append(i);
			vis[i]=true;
			dfs1(n,dep+1,k,path);
			//注意1.这里回溯不重置
			//这里加return，后面的不用去尝试
			return;
		}
	}
	//计算阶乘
	private void calculateFactorial(int n){
		factorial=new int[n+1];
		factorial[0]=1;
		for (int i = 1; i <=n ; i++) {
			factorial[i]=factorial[i-1]*i;
		}
	}

	/*有序列表
	* 和剪枝类似，一位一位的确定当前值填什么，其中，k/后面几位的阶乘，恰好等于候选数的下标
	* 选择后  k减去
	* 已经填好的数从列表中删去
	* 比如 n 4 k9
	* 第一次选8/6=1，选择并删去2，k-6=2,
	* 第二次选择2/2=1，选择3，k-2=0,删去3
	* 第三次选择0/1=0，k-0=0,选择删去1，
	* 最后一次，选择4选取4*/
	public String getPermutation3(int n, int k) {
		// 注意：相当于在 n 个数字的全排列中找到下标为 k - 1 的那个数，因此 k 先减 1
		k --;

		int[] factorial = new int[n];
		factorial[0] = 1;
		// 先算出所有的阶乘值
		for (int i = 1; i < n; i++) {
			factorial[i] = factorial[i - 1] * i;
		}

		// 这里使用数组或者链表都行
		List<Integer> nums = new LinkedList<>();
		for (int i = 1; i <= n; i++) {
			nums.add(i);
		}

		StringBuilder stringBuilder = new StringBuilder();

		// i 表示剩余的数字个数，初始化为 n - 1
		for (int i = n - 1; i >= 0; i--) {
			//选择k/未选数阶乘
			int index = k / factorial[i] ;
			//选择并删除
			stringBuilder.append(nums.remove(index));
			//k-阶乘数*index（几倍的阶乘）
			k -= index * factorial[i];
		}
		return stringBuilder.toString();
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
